Thực đơn
Phân_tích_LU Các thuật toánPhân tích LU về cơ bản là một dạng của phép khử Gaussian. Ta chuyển ma trận A thành ma trận tam giác trên U bằng cách khử các phần tử bên dưới đường chéo chính. Thuật toán Doolittle khử từng cột một bắt đầu từ bên trái, bằng cách nhân bên trái A với các ma trận tam giác dưới. Kết quả của thuật toán này là một ma trận tam giác dưới đơn vị và một ma trận tam giác trên. Thuật toán Crout hơi khác ở chỗ tạo thành một ma trận tam giác dưới và một ma trận tam giác trên đơn vị.
Phân tích LU sử dụng các thuật toán này yêu cầu khoảng 2n3 / 3 phép tính dấu chấm động.
Cho một ma trận N × N
A = ( a n , n ) {\displaystyle A=(a_{n,n})}ta định nghĩa
A ( 0 ) := A {\displaystyle A^{(0)}:=A}và lặp với n = 1,...,N-1 như sau.
Khử các phần tử bên dưới đường chéo chính của cột thứ ncủa A(n-1)bằng cách cộng vào dòng thứ i của ma trận này với dòng thứ n và nhân thêm hệ số
l i , n := − a i , n ( n − 1 ) a n , n ( n − 1 ) {\displaystyle l_{i,n}:=-{\frac {a_{i,n}^{(n-1)}}{a_{n,n}^{(n-1)}}}}với i = n + 1 , … , N {\displaystyle i=n+1,\ldots ,N} . Nói cách khác, ta nhân bên tráiA(n-1) với ma trận tam giác dưới
L n = ( 1 0 ⋱ 1 l n + 1 , n ⋱ ⋮ ⋱ 0 l N , n 1 ) . {\displaystyle L_{n}={\begin{pmatrix}1&&&&&0\\&\ddots &&&&\\&&1&&&\\&&l_{n+1,n}&\ddots &&\\&&\vdots &&\ddots &\\0&&l_{N,n}&&&1\\\end{pmatrix}}.}Đặt
A ( n ) := L n A ( n − 1 ) . {\displaystyle A^{(n)}:=L_{n}A^{(n-1)}.}Sau N-1 bước, ta đã khử tất cả các phần tử bên dưới đường chéo chính, và nhận được ma trận tam giác trênA(N-1). Phép phân tích LU được xác định bằng nhận xét rằng
A = L 1 − 1 L 1 A ( 0 ) = L 1 − 1 A ( 1 ) = L 1 − 1 L 2 − 1 L 2 A ( 1 ) = L 1 − 1 L 2 − 1 A ( 2 ) = … = L 1 − 1 … L N − 1 − 1 A ( N − 1 ) . {\displaystyle A=L_{1}^{-1}L_{1}A^{(0)}=L_{1}^{-1}A^{(1)}=L_{1}^{-1}L_{2}^{-1}L_{2}A^{(1)}=L_{1}^{-1}L_{2}^{-1}A^{(2)}=\ldots =L_{1}^{-1}\ldots L_{N-1}^{-1}A^{(N-1)}.}Ký hiệu ma trận tam giác trênA(N-1) là U, và L = L 1 − 1 … L N − 1 − 1 {\displaystyle L=L_{1}^{-1}\ldots L_{N-1}^{-1}} . Vì nghịch đảo của ma trận tam giác dưới 'Ln cũng là ma trận tam giác dưới, và tích hai ma trận tam giác dưới cũng là một ma trận tam giác dưới nên L là ma trận tam giác dưới cần tìm.Hơn nữa, nhận xét rằng
L = ( 1 0 − l 2 , 1 ⋱ 1 ⋮ − l n + 1 , n ⋱ ⋮ 1 − l N , 1 − l N , n − l N , N − 1 1 ) . {\displaystyle L={\begin{pmatrix}1&&&&&0\\-l_{2,1}&\ddots &&&&\\&&1&&&\\\vdots &&-l_{n+1,n}&\ddots &&\\&&\vdots &&1&\\-l_{N,1}&&-l_{N,n}&&-l_{N,N-1}&1\\\end{pmatrix}}.}Vậy ta có A = L U {\displaystyle A=LU} .
Rõ ràng là để thuật toán hoạt động được, cần phải đảm bảo a n , n ( n − 1 ) ≠ 0 {\displaystyle a_{n,n}^{(n-1)}\not =0} tại mỗi bước (xem công thức l i , n {\displaystyle l_{i,n}} ). Nếu giả sử này không đúng ở một bước nào đó, ta có thể hoán vị dòng thứ n với một dòng khác bên dưới nó để tiếp tục thuật toán. Đây là lý do mà phép phân tích LU tổng quát tương tự với phép phân tích P − 1 A = L U {\displaystyle P^{-1}A=LU} .
Thuật toán phân tích LUP của Cormen et al. là trường hợp tổng quát của phép phân tích Crout. Phần này trình bày thuật toán phân tích LUP.
Đoạn mã giả sau thể hiện từng bước của thuật toán phân tích LUP:
// A: input - ma trận ban đầu, kích thước n x n.// n: input - kích thước của A.// C: output - ma trận kích thước (n x n+1),...// với n cột đầu tiên chứa L và U,...// cột cuối cùng thể hiện ma trận hoán vị P.FUNCTION LUP(n, A; C) // khởi tạo C FOR i=1 TO n DO C[i;n+1] = i // khởi tạo p FOR j=1 TO n DO C[i,j] = A[i,j] END END FOR j=1 TO n-1 DO // với mỗi cột j Chọn phần tử khác 0 lớn nhất (phần tử neo) trong cột j. Gọi i là dòng chứa phần tử neo đó. IF không tìm được i THEN NGỪNG THUẬT TOÁN // Không có lời giải duy nhất END IF i ~= j THEN Đảo dòng i và j END FOR i = j + 1 TO n DO // với mỗi dòng bên dưới dòng thứ j t = C[i,j]/C[j,j] // thừa số C[i, j] = t FOR k = j+1 TO n DO // với mỗi cột bên phải cột j C[i,k] = C[i,k] - t*C[j,k] END END ENDEND
Nếu nhân hai ma trận bậc n có độ phức tạp M(n), trong đó M(n)≥na với a>2 nào đó, thì phép phân tích LU có thể được tính trong thời gian O(M(n)).[1] Nghĩa là, chẳng hạn dựa trên thuật toán Coppersmith–Winograd, ta có thể có thuật toán phân tích LU với độ phức tạp O(n2.376).
Thực đơn
Phân_tích_LU Các thuật toánLiên quan
Phân Phân loại sinh học Phân phối chuẩn Phân cấp hành chính Việt Nam Phân bón Phân loại giới Động vật Phân người Phân loại sao Phân tích kỹ thuật Phân cấp hành chính Hàn QuốcTài liệu tham khảo
WikiPedia: Phân_tích_LU http://www.mpi-hd.mpg.de/astrophysik/HEA/internal/... http://arxiv.org/abs/math.NA/0506382